package xiaohong.sort;

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;

public class QuickSortDemo {

    public static void main(String[] args) {

        List<Integer> nums = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            nums.add((int)(Math.random() * 100));
        }
        System.out.println("排序前" +nums);
        Date date = new Date();
        SimpleDateFormat formatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        System.out.println( "快速排序之前时间" +formatter.format(date));
//        quickSort(nums, 0, nums.size() - 1);
        quickSort(nums,0,nums.size()-1);
        Date date1 = new Date();
//        System.out.println( "快速排序之后时间" +formatter.format(date1));
        System.out.println("排序后" + nums);
    }

    public static void quickSort(List<Integer> nums , int left , int right) {
        if (left >= right) {
            return;
        }
        if (nums.size() <= 1) {
            return;
        }
        int l = left;
        int r = right;
        int pivot = nums.get(left);
        int temp = 0;
        while (l < r) {
            while (nums.get(r) > pivot) {
                r-- ;
            }
            while (nums.get(l) < pivot) {
                l++ ;
            }
            if (l >= r) {
                break;
            }
            temp = nums.get(l);
            nums.set(l, nums.get(r));
            nums.set(r, temp);

            if (nums.get(l) == pivot) {
                r -- ;
            }
            if (nums.get(r) == pivot) {
                l ++ ;
            }
        }
        if (l ==  r) {
            l ++ ;
            r -- ;
        }
        if (left < r) {
            quickSort(nums, left, r);
        }
        if (right > l) {
            quickSort(nums, l, right);
        }
    }




}
